package vj.tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BST {

	private Node root;

	class  Node {
		Node left;
		Node right;
		int data;
		int level;
		
		public Node(int newData) {
			left = null;
			right = null;
			data = newData;
		}
		
		public Node(int newData, int lvl) {
			left = null;
			right = null;
			data = newData;
			level = lvl;
		}
	}
	
	public BST() {
		root = null;
	}
	
	public Node getRoot() {
		return root;
	}
	
	public void insert(int data) {
		root = insert(root, data, 1);
	}

	private Node insert(Node root, int data, int level) {
		if(root == null) {
			root = new Node(data, level);
		} else {
			if(data <= root.data) {
				root.left = insert(root.left, data, ++level);
			} else {
				root.right = insert(root.right, data, ++level);
			}
		}
		return root;
	}
	
	public static void printInOrder(Node root) {
		printInOrder1(root);
	}
	
	private static void printInOrder1(Node node) {
		if(node == null) 
			return;
		printInOrder1(node.right);
		System.out.println(node.data);
		printInOrder1(node.left);
		
	}

	public static void printPostOrder(Node root) {
		printPostOrder1(root);
	}

	private static void printPostOrder1(Node node) {
		if(node == null) 
			return;
		printPostOrder1(node.left);
		printPostOrder1(node.right);
		System.out.println(node.data);
		
	}
	
	public static void printLevelWise(Node root) {
		Queue<Node> q = new LinkedList<Node>();
		Queue<Node> q1 = new LinkedList<Node>();
		q.add(root);
		boolean done = false;
		while(!done) {
			while(!q.isEmpty()) {
				Node top = q.remove();
				if(top.left != null)
					q1.add(top.left);
				if(top.right != null)
					q1.add(top.right);
				System.out.print(top.data + " ");
			}
			System.out.println();
			while(!q1.isEmpty()) {
				Node top = q1.remove();
				if(top.left != null)
					q.add(top.left);
				if(top.right != null)
					q.add(top.right);
				System.out.print(top.data + " ");
			}
			System.out.println();
			if(q.isEmpty() && q1.isEmpty())
				done = true;
		}
		/*Stack<Node> q = new Stack<Node>();
		q.add(root);
		while(!q.isEmpty()) {
			Node top = q.pop();
			if(top.left != null)
				q.add(top.left);
			if(top.right != null)
				q.add(top.right);
			System.out.println(top.data);
		}*/
	}
	
	public static void printCircualarLevelWise(Node root) {
		Stack<Node> stk1 = new Stack<Node>();
		Stack<Node> stk2 = new Stack<Node>();
		stk1.add(root);
		boolean finish = false;
		while(!finish) {
			while(!stk1.isEmpty()) {
				Node top = stk1.pop();
				if(top.right != null)
					stk2.add(top.right);
				if(top.left != null)
					stk2.add(top.left);
				System.out.println(top.data);
			}
			while(!stk2.isEmpty()) {
				Node top = stk2.pop();
				if(top.left != null)
					stk1.add(top.left);
				if(top.right != null)
					stk1.add(top.right);
				System.out.println(top.data);
			}
			if(stk1.isEmpty() && stk2.isEmpty())
				finish = true;
		}
	}
	
	public boolean isMirrorImage(Node root) {
		return false;
	}
	
	public static void printPreorder(Node root) {
		printPreorder1(root);
	}
	
	public static void printPreorderItr(Node root) {
		Stack<Node> stk = new Stack<Node>();
		stk.push(root);
		while(!stk.isEmpty()) {
			Node top = stk.pop();
			System.out.println(top.data);
			if(top.right != null)
				stk.push(top.right);
			if(top.left != null)
				stk.push(top.left);
		}
	}

	private static void printPreorder1(Node node) {
		if(node == null)
			return;
		System.out.println(node.data);
		printPreorder1(node.left);
		printPreorder1(node.right);
		
	}
	
	public void printTree() {
		printTree(root);
	}
	
	private void printTree(Node node) {
		if(node == null)
			return;
		printTree(node.left);
		System.out.print(node.data + " ");
		printTree(node.right);
	} 
	
	public void printReverseInorder() {
		printReverseInorder(root);
	} 
	private void printReverseInorder(Node node) {
		if(node == null)
			return;
		printTree(node.right);
		System.out.print(node.data + " ");
		printTree(node.left);
	} 
	
	
	public void printTreeLevelwise1() {
		printTreeLevelwise1(root);
	}
	
	private void printTreeLevelwise1(Node node) {
		if(node == null)
			return;
		// A Queue is needed for processing
		// We have to ensure that null values are not pushed into the queue since ther is no null check
		Queue<Node> q = new LinkedList<Node>();
		q.add(node);
		int curlevel = 1;
		while(!q.isEmpty()) {
			Node n = (Node)q.remove();
			if(curlevel != n.level) {
				curlevel++;
				System.out.println("");
			}
			System.out.print(n.data + " ");
			if(n.left != null)
				q.add(n.left);
			if(n.right != null)
				q.add(n.right);
		}
	}
	
	public boolean lookup(int data) {
		return lookup(root, data);
	}

	public boolean find(int data) {
		return lookup(root, data);
	}
	
	private boolean lookup(Node node, int data) {
		if(node == null)
			return false;
		if(node.data == data)
			return true;
		if(data < node.data)
			return lookup(node.left, data);
		else
			return lookup(node.right, data);
		
	}
	
	private Node findMin(Node node) {
		if(node == null)
			throw new IllegalArgumentException("Argument cannot be null");
		while(node.left != null)
			node = node.left;
		return node;
	}
	
	
	/*
	 * This method removes the minimum element from the subtree rooted at t
	 */
	private void removeMin(Node t) {
		if(t == null)
			throw new IllegalArgumentException("Method cannot be called on null");
		if(t.left != null) {
			
		}
			
	}
	
	
	/*
	 * Any tweaks possible for Inorder like maintaingin static int;
	 */
	public static int kthSmallest(Node root) {
		return 0;
	}
}
